package leetcode;

import java.util.LinkedList;

public class Lc739 {



    public int[] dailyTemperatures(int[] temperatures) {

        LinkedList<Integer> temper = new LinkedList<>();
        LinkedList<Integer> index = new LinkedList<>();
        temper.push(temperatures[0]);
        index.push(0);
        int[] ans = new int[temperatures.length];
        for (int i = 1; i < temperatures.length; i++) {
            while (!temper.isEmpty() && temperatures[i] > temper.peek()) {
                int idx = index.pop();
                temper.pop();
                ans[idx] = i - idx;
            }
            temper.push(temperatures[i]);
            index.push(i);
        }
        while (!index.isEmpty()) {
            ans[index.pop()] = 0;
        }

        return ans;
    }

    public static void main(String[] args) {
        Lc739 lc739 = new Lc739();
        lc739.dailyTemperatures(new int[]{73,74,75,71,69,72,76,73});
    }

}
